|
A regular language is said to be star-free if it can be described by a regular expression constructed from the letters of the alphabet, the empty set symbol, all boolean operators – including complementation – and concatenation but no Kleene star.〔Lawson (2004) p.235〕 For instance, the language of words over the alphabet that do not have consecutive a's can be defined by , where denotes the complement of a subset of . The condition is equivalent to having generalized star height zero. An example of a regular language which is not star-free is . Marcel-Paul Schützenberger characterized star-free languages as those with aperiodic syntactic monoids.〔Lawson (2004) p.262〕 They can also be characterized logically as languages definable in FO(), the first-order logic over the natural numbers with the less-than relation, as the counter-free languages and as languages definable in linear temporal logic. All star-free languages are in uniform AC0. ==See also== *Star height *Generalized star height problem *Star height problem 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Star-free language」の詳細全文を読む スポンサード リンク
|